package com.zjj.lbw.interview.tree;

import com.zjj.lbw.interview.common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhanglei.zjj
 * @description 二叉树中序遍历-递归
 * @date 2023/9/3 11:47
 */
public class BinaryTreeMidOrder {
    /**
     * 中序遍历-递归
     * @param root
     */
    public static void midorderRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        midorderRecursion(root.left);
        System.out.println(root.val);
        midorderRecursion(root.right);
    }

    /**
     * 中序遍历-迭代
     * @param root
     */
    public static void midorderIteration(TreeNode root) {
        if (root != null) {
            Deque<TreeNode> stack = new LinkedList<>();
            while(!stack.isEmpty() || root != null)  {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    TreeNode headNode = stack.pop();
                    System.out.println(headNode.val);
                    root = headNode.right;
                }

            }
        }
    }

    /**
     * 中序遍历-morris
     * @param root
     */
    public static void midorderMorris(TreeNode root) {
        if (root != null) {
            TreeNode mostRight = null;
            while (root != null) {
                mostRight = root.left;
                if (mostRight != null) {
                    while (mostRight.right != null && mostRight.right != root) {
                        mostRight = mostRight.right;
                    }
                    if (mostRight.right == null) {
                        mostRight.right = root;
                        root = root.left;
                        continue;
                    }
                    if (mostRight.right == root) {
                        mostRight.right = null;
                    }
                }
                System.out.println(root.val);
                root = root.right;
            }
        }
    }

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        midorderRecursion(node1);
//        midorderIteration(node1);
        midorderMorris(node1);
    }
}
